<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ -->
<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ --><!-- saved from url=(0058)http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ -->
  

  <meta name="ProgId" content="Word.Document">

  <meta name="Generator" content="Microsoft Word 10">

  <meta name="Originator" content="Microsoft Word 10">

  <link rel="File-List" href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/Default_files/filelist.xml">

  <link rel="Edit-Time-Data" href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/Default_files/editdata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->


  <title>Multiprocessor Synchronization Class Homepage</title>
  </head><body style="" bgcolor="white" lang="EN-US" link="blue" vlink="blue"><o:smarttagtype namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="place"></o:smarttagtype>
  <o:smarttagtype namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="PlaceType"></o:smarttagtype>
  <o:smarttagtype namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="PlaceName"></o:smarttagtype>
  <o:smarttagtype namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="time"></o:smarttagtype>
  <o:smarttagtype namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="date"></o:smarttagtype><!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>shanir</o:Author>
  <o:Template>Normal</o:Template>
  <o:LastAuthor>shanir</o:LastAuthor>
  <o:Revision>167</o:Revision>
  <o:TotalTime>504</o:TotalTime>
  <o:Created>2003-03-19T11:57:00Z</o:Created>
  <o:LastSaved>2003-06-08T07:00:00Z</o:LastSaved>
  <o:Pages>1</o:Pages>
  <o:Words>2205</o:Words>
  <o:Characters>11027</o:Characters>
  <o:Company>School of CS, Tel-Aviv University</o:Company>
  <o:Lines>91</o:Lines>
  <o:Paragraphs>26</o:Paragraphs>
  <o:CharactersWithSpaces>13206</o:CharactersWithSpaces>
  <o:Version>10.2625</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:SpellingState>Clean</w:SpellingState>
  <w:GrammarState>Clean</w:GrammarState>
  <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
 </w:WordDocument>
</xml><![endif]--><!--[if !mso]><object
 classid="clsid:38481807-CA0E-42D2-BF39-B33AF135CC4D" id=ieooui></object>
<style>
st1\:*{behavior:url(#ieooui) }
</style>
<![endif]-->

  <style>
<!--
 /* Font Definitions */
 @font-face
	{font-family:Verdana;
	panose-1:2 11 6 4 3 5 4 4 2 4;
	mso-font-charset:0;
	mso-generic-font-family:swiss;
	mso-font-pitch:variable;
	mso-font-signature:536871559 0 0 0 415 0;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0cm;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
h1
	{mso-margin-top-alt:auto;
	margin-right:0cm;
	mso-margin-bottom-alt:auto;
	margin-left:0cm;
	mso-pagination:widow-orphan;
	mso-outline-level:1;
	font-size:24.0pt;
	font-family:"Times New Roman";
	font-weight:bold;}
h2
	{mso-margin-top-alt:auto;
	margin-right:0cm;
	mso-margin-bottom-alt:auto;
	margin-left:0cm;
	mso-pagination:widow-orphan;
	mso-outline-level:2;
	font-size:18.0pt;
	font-family:"Times New Roman";
	font-weight:bold;}
a:link, span.MsoHyperlink
	{color:blue;
	text-decoration:underline;
	text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
	{color:blue;
	text-decoration:underline;
	text-underline:single;}
p
	{mso-margin-top-alt:auto;
	margin-right:0cm;
	mso-margin-bottom-alt:auto;
	margin-left:0cm;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
address
	{margin:0cm;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	font-style:italic;}
p.abstract, li.abstract, div.abstract
	{mso-style-name:abstract;
	mso-margin-top-alt:auto;
	margin-right:0cm;
	mso-margin-bottom-alt:auto;
	margin-left:7.5pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:Verdana;
	mso-fareast-font-family:"Times New Roman";
	mso-bidi-font-family:"Times New Roman";}
span.SpellE
	{mso-style-name:"";
	mso-spl-e:yes;}
span.GramE
	{mso-style-name:"";
	mso-gram-e:yes;}
@page Section1
	{size:612.0pt 792.0pt;
	margin:72.0pt 90.0pt 72.0pt 90.0pt;
	mso-header-margin:36.0pt;
	mso-footer-margin:36.0pt;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
 /* List Definitions */
 @list l0
	{mso-list-id:41101212;
	mso-list-template-ids:2030370384;}
@list l0:level1
	{mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level2
	{mso-level-tab-stop:72.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level3
	{mso-level-tab-stop:108.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level4
	{mso-level-tab-stop:144.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level5
	{mso-level-tab-stop:180.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level6
	{mso-level-tab-stop:216.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level7
	{mso-level-tab-stop:252.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level8
	{mso-level-tab-stop:288.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l0:level9
	{mso-level-tab-stop:324.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1
	{mso-list-id:1083258444;
	mso-list-template-ids:2006330832;}
@list l1:level1
	{mso-level-tab-stop:36.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level2
	{mso-level-tab-stop:72.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level3
	{mso-level-tab-stop:108.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level4
	{mso-level-tab-stop:144.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level5
	{mso-level-tab-stop:180.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level6
	{mso-level-tab-stop:216.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level7
	{mso-level-tab-stop:252.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level8
	{mso-level-tab-stop:288.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l1:level9
	{mso-level-tab-stop:324.0pt;
	mso-level-number-position:left;
	text-indent:-18.0pt;}
@list l2
	{mso-list-id:1441955303;
	mso-list-template-ids:1377740786;}
@list l3
	{mso-list-id:1569917055;
	mso-list-template-ids:1396335124;}
ol
	{margin-bottom:0cm;}
ul
	{margin-bottom:0cm;}
-->
  </style><!--[if gte mso 10]>
<style>
 /* Style Definitions */
 table.MsoNormalTable
	{mso-style-name:"Table Normal";
	mso-tstyle-rowband-size:0;
	mso-tstyle-colband-size:0;
	mso-style-noshow:yes;
	mso-style-parent:"";
	mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
	mso-para-margin:0cm;
	mso-para-margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:10.0pt;
	font-family:"Times New Roman";}
</style>
<![endif]--><!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="46082"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1"/>
 </o:shapelayout></xml><![endif]-->









<div class="Section1">

<h1 style="text-align: center;" align="center">Multiprocessor Programming </h1>


<h1 style="text-align: center;" align="center">CS 0368-4061-01</h1>


<h1 style="text-align: center;" align="center">Spring 2007</h1>


<p class="MsoNormal" style="text-align: center;" align="center"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/CourseLogo.gif"><span style="color: windowtext; text-decoration: none;"><img id="_x0000_i1025" src="./Multiprocessor Synchronization Class Homepage_files/CourseLogo.gif" border="0" height="184" width="382"></span></a></p>


<p style="text-align: center;" align="center"><a href="http://www.cs.tau.ac.il/~shanir/">Handouts</a>
| <a href="http://www.cs.tau.ac.il/~shanir/">Mail</a>
| <a href="http://www.cs.tau.ac.il/~shanir">Reference</a></p>


<p style="text-align: center;"><span style="font-style: italic;">The course will be based on the book The Art of Multiprocessor Programming by</span><br style="font-style: italic;">
<span style="font-style: italic;">Maurice Herlihy and Nir Shavit, to be published by Morgan Kaufmann Publishers, Copyright</span><br style="font-style: italic;">
<span style="font-style: italic;">2006 Elsevier Inc. All rights reserved.</span></p>
<p style="font-weight: bold;"><big><big>Why Multiprocessor &nbsp;Programming?</big></big></p>
<p>The computer industry is undergoing a paradigm shift. Chip
manufacturers are shifting development resources away from
single-processor chips to a new generation of multi-processor chips
known as <span style="font-style: italic;">multicores</span>.<br>
<br>
This fundamental change in our core computing architecture will require
a fundamental change in how we program. The art of multiprocessor
programming, currently mastered by few, is more complex than
programming uniprocessor machines, and requires an understanding of new
computational principles, algorithms, and programming tools.<br>
<br>
Concurrent computation on uniprocessor and multiprocessor architectures
have many aspects in common. The key issue that distinguishes
multiprocessor programming from concurrent uniprocessor programming is
the need to understand how concurrent computations on separate
processors coordinate with one another, a broad and intricate problem
area we call&nbsp;multiprocessor synchronization.<br>
<br>
There are no textbooks and few reference books addressing how to
program multiprocessors, and none cover the fundamental issues of
synchronization and how it affects data structure design. Most
engineers must learn the tricks of the trade by asking help from more
experienced friends and through a laborious trial and error process.
This course aims to change this state of affairs, providing a
comprehensive presentation of the principles and tools available for
programming multiprocessor machines.<br>
<br>
<big><big><span style="font-weight: bold;">The Course</span></big></big><br>
<br>
The course will approach multiprocessor synchronization from two
complementary directions. In the first part of the book, we focus on <span style="font-style: italic;">foundations</span>: what&nbsp;<span style="font-style: italic;"> </span>do
our programs and machines need to provide in order to ensure that
concurrent programs do what we expect. We use an idealized model of
computation in which multiple concurrent&nbsp;<span style="font-style: italic;">threads</span> manipulate a set of shared<span style="font-style: italic;"> objects</span>. This model is essentially the model presented by standard Java(TM) or C++ threads packages.<br>
<br>
The foundations section is intended to build up the reader's intuition
and confidence in understanding and reasoning about concurrency. We
approach this goal using examples, counter-examples, models, and
exercises. These elements are laid out in a structured and progressive
manner, from simple machine instructions to powerful universal
constructions, the equivalent of Turing machines for multiprocessors.<br>
<br>
The second part of the course will be concerneed with <span style="font-style: italic;">performance</span>.
Reasoning about the performance of concurrent programs and data
structures is very different in flavor from reasoning about their
sequential counterparts. Sequential programming is based on a
well-established and well-understood set of abstractions. There is
little or no need to understand the specifics of the underlying
architecture. In multiprocessor programming, by contrast, there are no
such well-established abstractions. It is impossible to reason
effectively about the performance of a concurrent data structure
without understanding the fundamentals of the underlying architecture.<br>
<br>
The performance part of the course will revisit many of the issues
first raised in the correctness section, but in a more realistic model
that exposes those aspects of the underlying architecture that most
influence performance. The course then goes through a sequence of
fundamental data structures, the concurrent analogs of the data
structures found in any undergraduate data structures course. These
data structures are introduced in an incremental way, each one
extending the techniques developed for its predecessors. Each of these
data structures is useful in and of itself as a reference. Moreover, by
the end, the student will have built up a solid understanding of the
fundamentals of concurrent data structure design, and should be
well-prepared to design and implement his or her own concurrent data
structures.<br>
</p>
<p><big><big><span style="font-weight: bold;">Breif Outline </span></big></big></p>


<p>This is an undergraduate level course open to&nbsp;graduates.
Students are expected to have completed courses in data structures and
have an understanding of basic computability and complexity
theory.&nbsp; </p>


<p>Topics covered in the course include but are not limited to: </p>


<ol start="1" type="1">

 <li class="MsoNormal" style="">Software locking algorithms
     and lock-based data structures.</li>
  <li class="MsoNormal" style="">Multiprocessor and Multicore architetcures.</li>

 <li class="MsoNormal" style="">Wait-free and Lock-free
     algorithms. </li>

 <li class="MsoNormal" style="">Computational power
     evaluation of synchronization operations, from <span class="SpellE">test&amp;set</span>
     to universal operations such as load-linked/store-conditional. </li>

 <li class="MsoNormal" style="">Contention and
     Bottlenecking. </li>

 <li class="MsoNormal" style="">Concurrent data structures:
     queues, stacks, linked lists, hash tables, search trees. </li>

 <li class="MsoNormal" style="">Dynamic Load Balancing.</li>
  <li class="MsoNormal" style="">Transactional Memory.</li>
  <span style="font-family: &quot;Times New Roman&quot;;"><br>
  </span>
</ol>


<p class="MsoNormal">This course will be offered by <a href="http://cs.tau.ac.il/~shanir"><span class="SpellE">Nir</span> <span class="SpellE">Shavit</span></a> in the <span class="GramE">Spring</span> term of
2007. </p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<p class="MsoNormal" style="text-align: center;" align="center"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal"><b><i><u><span style="color: red;">Important Messages:</span></u></i></b></p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>
<br>
<p class="MsoNormal"><b><span style="color: rgb(51, 51, 51);">&nbsp;<o:p></o:p></span></b></p>


<p class="MsoNormal"><span style="">&nbsp; </span><a name="handout"></a></p>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<h2><big><big>****OLD</big></big> Lecture Notes and Slides (PDF and <span class="SpellE">Powerpoint</span>)&nbsp;<big><big>OLD****</big></big></h2>




<blockquote style="margin-top: 5pt; margin-bottom: 5pt;">
  <p class="MsoNormal"><b><span style="font-size: 14pt;">Part1: Foundations<o:p></o:p></span></b></p>


  <p class="MsoNormal"><b><span style="font-size: 14pt;">----------------------------------------------------------------------------------------------------------------<o:p></o:p></span></b></p>


  <p class="MsoNormal"><b><o:p>&nbsp;</o:p></b></p>


  <p class="MsoNormal"><b>Lecture 1: </b>Introduction, Administrative Remarks.</p>


</blockquote>


<p class="MsoNormal" style="margin-left: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/intro/slides/intro.pps">Lecture
1 Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/intro/notes/intro2.2.pdf">Lecture
1 <span class="GramE">Notes</span><span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal"><b><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>Lecture
2: </b>Mutual Exclusion (last updated <st1:date year="2003" day="29" month="3">3/29/2003</st1:date>
<st1:time minute="13" hour="17">5:13:06 PM</st1:time>).</p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal" style="margin-left: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/mutex/slides/mutex2.pps">Lecture
2 Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/mutex/notes/mutex2.pdf">Lecture
2 Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="margin-left: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal"><b><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>Lecture
3: </b>Concurrent Objects and <span class="SpellE">Linearizability</span> (last
updated 3/29/2003 5:13:18 PM).</p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal" style="margin-left: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/linear/slides/linearizable.pps">Lecture3
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/linear/notes/linear.pdf">Lecture3
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="margin-left: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 4: </b>Foundations of
Shared <span class="GramE">Memory<span style="">&nbsp; </span>(</span>last
updated <st1:date year="2003" day="29" month="3">3/29/2003</st1:date> <st1:time minute="13" hour="17">5:13:29 PM</st1:time><b>)<o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/register/slides/register.pps">Lecture4
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/register/notes/register.pdf">Lecture4
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 5: </b>The Relative
Power of Synchronization <span class="GramE">Methods<span style="">&nbsp; </span>(</span>last updated <st1:date year="2003" day="4" month="12">4/12/2003</st1:date> <st1:time minute="40" hour="11">11:40:18
 AM</st1:time><b>)<o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/waitfree/slides/waitfree.pps">Lecture5
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/waitfree/notes/consensus.pdf">Lecture5
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 6: </b>The
Universality of <span class="GramE">Consensus<span style="">&nbsp;
</span>(</span>last updated <st1:date year="2003" day="4" month="12">4/12/2003</st1:date>
<st1:time minute="39" hour="11">11:39:52 AM</st1:time><b>)<o:p></o:p></b></p>


<p class="MsoNormal"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/slides/universal.pps">Lecture6
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/notes/universal.pdf">Lecture6
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><span style="font-size: 14pt;">Part2:
Performance<o:p></o:p></span></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><span style="font-size: 14pt;">----------------------------------------------------------------------------------------------------------------<o:p></o:p></span></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 7: </b>Spin Locks and
Contention <span class="GramE">Management<span style="">&nbsp;
</span>(</span>last updated <st1:date year="2003" day="11" month="5">Sunday,
 May 11, 2003</st1:date><b>)<o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/spin/slides/spin.pps">Lecture7
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/spin/notes/spin.pdf">Lecture7
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 8: </b>Shared Counting
and <span class="GramE">Parallelism<span style="">&nbsp; </span>(</span>last
updated Wednesday 5/14/2003 <st1:time minute="2" hour="17">5:02:06 PM</st1:time><b>)<o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/counting/slides/counting.pps">Lecture8
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/counting/notes/counting.pdf">Lecture8
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 9: </b>Diffracting
Trees, Distribution, and Layout (last updated 5/21/2003 3:59:43 PM<b>)<o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/diffracting/slides/diffracting.pps">Lecture9
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/diffracting/notes/diffracting.pdf">Lecture9
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 10: </b>Barriers and
Synchronized <span class="GramE">Execution<span style="">&nbsp;
</span>(</span>last updated <st1:date year="2003" day="25" month="5">5/25/2003</st1:date>
<st1:time minute="58" hour="15">3:58:08 PM</st1:time><b>)<o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/barrier/slides/barrier.pps">Lecture10
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/barrier/notes/mcs.ps">Lecture10
Notes</a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 11: </b>Stacks,
Queues, Lists, and the ABA problem <span style="color: red;">(not updated yet<b>)<o:p></o:p></b></span></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/slides/universal.pps">Lecture11
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/notes/universal.pdf">Lecture11
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 12: </b>Concurrent <span class="GramE">Hashing<span style="">&nbsp; </span><span style="color: red;">(</span></span><span style="color: red;">not updated yet<b>)<o:p></o:p></b></span></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/slides/universal.pps">Lecture12
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/notes/universal.pdf">Lecture12
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 13: </b>Load <span class="GramE">Balancing<span style="">&nbsp; </span><span style="color: red;">(</span></span><span style="color: red;">updated </span><st1:date year="2003" day="25" month="5"><span style="color: red;">5/25/2003</span></st1:date><span style="color: red;"> </span><st1:time minute="59" hour="15"><span style="color: red;">3:59:14 PM</span></st1:time><span style="color: red;">)</span><b><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/steal/slides/steal.pps">Lecture13
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/steal/notes/steal.pdf">Lecture13
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><span style="font-size: 14pt;">Part3:
Advanced Topics<o:p></o:p></span></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><span style="font-size: 14pt;">----------------------------------------------------------------------------------------------------------------<o:p></o:p></span></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 14: </b>Room Synchronization<b>
</b><span style="color: red;">(not updated yet<b>)<o:p></o:p></b></span></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/slides/universal.pps">Lecture14
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/notes/universal.pdf">Lecture14
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b>Lecture 15: </b>Transactional
Memory and Optimistic Synchronization<b> </b><span style="color: red;">(not
updated yet<b>)<o:p></o:p></b></span></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/slides/universal.pps">Lecture15
Slides</a><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/universal/notes/universal.pdf">Lecture15
Notes<span style="font-weight: normal;">&nbsp;</span></a><o:p></o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="margin-left: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="text-indent: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal" style="margin-left: 36pt;"><b><o:p>&nbsp;</o:p></b></p>


<p class="MsoNormal"><b><o:p>&nbsp;</o:p></b></p>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<h2><a name="mail"></a>Homework Assignments</h2>


<p class="MsoNormal"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/homework01.pdf"><span class="GramE"><b>Homework 1</b></span></a><span class="GramE"> due on </span><st1:date year="2003" day="6" month="4"><span class="GramE">06/04/2003</span></st1:date><span class="GramE"> at </span><st1:time minute="0" hour="12"><span class="GramE">12PM</span></st1:time><span class="GramE">.</span><span style="">&nbsp; </span><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/solution01.doc"><b>Solution
1</b></a> posted on <st1:date year="2003" day="11" month="5">5/11/2003</st1:date>
<st1:time minute="36" hour="14">2:36:54 PM</st1:time>. </p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/homework2.pdf"><span class="GramE"><b>Homework 2</b></span></a><span class="GramE"> due on </span><st1:date year="2003" day="28" month="4"><span class="GramE">28/04/2003</span></st1:date><span class="GramE"> at </span><st1:time minute="0" hour="0"><span class="GramE">12AM</span></st1:time><span class="GramE">.</span> <a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/solution02.doc"><b>Solution
2</b></a> posted on <st1:date year="2003" day="6" month="8">6/8/2003</st1:date>
<st1:time minute="54" hour="8">8:54:01 AM</st1:time>.</p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/homework3.pdf"><span class="GramE"><b>Homework 3</b></span></a><span class="GramE"> due on </span><st1:date year="2003" day="22" month="5"><span class="GramE">22/05/2003</span></st1:date><span class="GramE"> at </span><st1:time minute="0" hour="0"><span class="GramE">12AM</span></st1:time><span class="GramE">.</span></p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/homework4-nir.pdf"><span class="GramE"><b>Homework 4</b></span></a><span class="GramE"> due on </span><st1:date year="2003" day="4" month="6"><span class="GramE">04/06/2003</span></st1:date><span class="GramE"> at </span><st1:time minute="0" hour="0"><span class="GramE">12AM</span></st1:time><span class="GramE">.</span></p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<p class="MsoNormal"><b><span style="color: red;"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/final-nir-2003-2.pdf"><span class="GramE">FINAL EXAM</span></a><span class="GramE">.</span> Good luck. You must return it to <span class="SpellE">Larisa</span>
the dept secretary before </span></b><st1:time minute="0" hour="16"><b><span style="color: red;">4PM</span></b></st1:time><b><span style="color: red;"> or the
end of her office hours on Sunday June 15<sup>th</sup> in case they end before </span></b><st1:time minute="0" hour="16"><b><span style="color: red;">4PM</span></b></st1:time><b><span style="color: red;">.<o:p></o:p></span></b></p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<h2>Grades</h2>


<p class="MsoNormal"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/homework/synch-grades-ex1-3.xls"><b>Homework
Grades</b></a> for homework assignments 1-<span class="GramE">3<span style="">&nbsp; </span>(</span>posted on <st1:date year="2003" day="8" month="6">Sunday, June 08, 2003</st1:date>) </p>


<p class="MsoNormal" style=""><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></p>


<h2 style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</h2>


<h2>Questions, Answers, and Comments</h2>


<p class="MsoNormal"><a href="http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/questions-comments/qa.txt"><b>Q&amp;A</b></a><span style="">&nbsp; </span>(last updated <st1:date year="2003" day="8" month="6">Sunday, June 08, 2003</st1:date>)</p>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<p><b><span style="font-size: 18pt;">Mailing List</span></b> </p>


<p><b>Attending Students: please </b>send <a href="mailto:shanir@cs.tau.ac.il">shanir@cs.tau.ac.il</a>
an email titled REGISTERING TO MULT SYNCH with your name, email, and a phone
number. </p>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<h2><a name="reference"></a>Links and References</h2>


<ol start="1" type="1">

 <li class="MsoNormal" style="">Information and links to
     related material can be found off the <a href="http://www.podc.org/podc2003/">PODC'03 Homepage</a>, the homepage of
     the ACM Symposium on the Principles of Distributed Computing, the <a href="http://www.cs.dartmouth.edu/SPAA/">SPAA 2003 homepage</a>, the
     homepage of the ACM Symposium on Parallel Algorithms and Architectures, or
     <a href="http://www.enseeiht.fr/~disc03/">DISC 03</a>, the homepage of the
     17th International Symposium on <span class="SpellE">DIStributed</span>
     Computing (DISC 2003). </li>

 <li class="MsoNormal" style="">See also the homepage of
     the <st1:place><st1:placename>Tel-Aviv</st1:placename> <st1:placetype>University</st1:placetype></st1:place>
     <a href="http://www.cs.tau.ac.il/~msl/">Multiprocessor Synchronization Lab</a>.
     </li>

</ol>


<div style="margin-top: 5pt; margin-bottom: 5pt;">

<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


</div>


<p class="MsoNormal"><o:p>&nbsp;</o:p></p>


<address><span class="GramE">Last updated on </span><st1:date year="2003" day="5" month="5"><span class="GramE">Monday, May 05, 2003</span></st1:date><span class="GramE"> by <a href="http://antares.math.tau.ac.il/~shanir"><span class="SpellE">Nir</span> <span class="SpellE">Shavit</span>.</a></span></address>


<p class="MsoNormal" style=""><a href="http://antares.math.tau.ac.il/~shanir"><span style="color: windowtext; text-decoration: none;"><span style=""></span></span><o:p></o:p></a></p>


<p class="MsoNormal"><a href="http://antares.math.tau.ac.il/~shanir"><span style="color: windowtext; text-decoration: none;"><span style=""></span></span><o:p></o:p></a></p>


<p class="MsoNormal"><a href="http://antares.math.tau.ac.il/~shanir"><span style="color: windowtext; text-decoration: none;"><span style=""></span></span><o:p></o:p></a></p>


<p class="MsoNormal"><a href="http://antares.math.tau.ac.il/~shanir"><span style="color: windowtext; text-decoration: none;"><span style=""></span></span><o:p></o:p></a></p>


<p class="MsoNormal"><a href="http://antares.math.tau.ac.il/~shanir"><span style="color: windowtext; text-decoration: none;"><span style=""></span></span><o:p></o:p></a></p>


</div>




</body></html>